class Solution {
public:
    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };
    bool dfs(vector<vector<char>>& board, string& word, int pos, int i, int j)
    {
        if(pos == word.size() - 1 && board[i][j] == word[pos]) return true;
        if(board[i][j] != word[pos])
            return false;
        
        char tmp = board[i][j];
        board[i][j] = ' ';
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && y >= 0 && x < board.size() && y < board[0].size() && board[x][y] != ' ')
            {
                if(dfs(board, word, pos + 1, x, y) == true)
                    return true;
            }
        }
        board[i][j] = tmp;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0; i < board.size(); i++)
        {
            for(int j = 0; j < board[0].size(); j++)
            {
                if(dfs(board, word, 0, i, j))
                    return true;
            }
        }
        return false;
    }
};